← Back to Home
[SST-2028] NoSQL Internals - LSM Tree and Bloom Filter and Sparse Index

For any suggestions or feedback regarding these notes,

please contact Pragy Agarwal

LSM Visualization

https://kshitijmishra23.github.io/lsm-tree-visualizer/

        https://github.com/kshitijmishra23/lsm-tree-visualizer

Optimizing Disk Reads - Sparse Indices

Binary Search O(log n) is ultra fast compared to Linear Search O(n)

Consider a database with 1 trillion entries.

Binary Search takes O(log2 1 trillion) = 40 steps

Linear Search takes = 1 trillion steps

Binary Search is 25 billion times faster than Linear Search in this example!

Binary Searching the SSTable is expensive, because the SSTable size can be large.

Typical WAL size = 100MB

size SSTable on Level 1 <= 100MB (because it is compacted from the WAL file)

size SSTable on Level 2 <= 200MB (because it is compacted from 2 SSTables from Level 1)

size SSTable on Level 3 <= 400MB (because it is compacted from 2 SSTables from Level 2)

...

Consider an SSTable of size 100GB. Assume each entry (key, value, timestamp) on average is 100 bytes.

Number of entries in the SSTable = 100G bytes / 100 bytes = 1G = 1 billion

For a binary search, # iterations = log2 (109) = 9 * log2(10) ≈ 30 iterations

Each iteration on the disk is a random read. Each random read takes ~18ms

Total time for checking 1 SSTable = 30 * 18ms = 540 ms

If we have 10 SSTables, then each read potentially takes 5.4 seconds worst case.

Therefore, we need an index.

Idea

What if we get rid of the binary search O(log n) and instead use an in-memory (RAM) index to exactly pin-point the location of an entry in the SSTable O(1).

This will give us a 30x speedup (in the above example of SSTable with 1 billion entries)

So each SSTable lookup is now just 18 ms, and since you’ve 10 SSTables, your reads take 180ms total worst case (30x faster compared to 5.4 seconds).

Notice that this is not always the case — 90% of the reads are being served directly from the RAM thanks to the MemTable which acts as a read cache. Reading from the MemTable takes 0.1ms at worst.

Effective read latency is actually much better. Only 10% of you times you need to hit the disk, and in the worst case of that, you will hit 180ms of read latency

Effective read latency ~20ms on average.

Full Index

Instead of binary searching the SSTable, what if we maintain a hashmap of {key: offset} in the RAM for each SSTable.

Given a key, we don't have to binary search the SSTable.

We just check the Index to find if the key is there in the SSTable. If the key is there in the index, the index will give us the exact offset within the file to read.

Reads: O(1) per SSTable.  30x speedup

However maintaining a full index in the RAM will take a lot of space.

Our SSTable has 1 billion entries. So the index will also have 1 billion entries.

For each entry we will need to store the key (say 20 bytes on avg), and the offset (8 bytes)

Total = 1 billion entries * 28 bytes / entry = 28GB for 1 SSTable.

For 10 SSTables, it will be 280GB.

That's too much RAM.

Sparse Index

Sparse Index is built for each SSTable, and is stored in the RAM.

Sparse Index is built when the SSTable is created.

Because data is always read/written in blocks, we don't need to maintain an index of all the keys in the SSTables.

We can just maintain an index of the first key of each block.

Typical block size: 4KB

Assume each entry (key, value, timestamp) on average is 100 bytes.

Keys in each block 4K bytes / 100 bytes = 40 keys 

Our sparse index will be smaller in size by a factor of 40.

Sparse Index will now only have 25 million entries (~100MB) for a 100GB SSTable.

Sparse Index is just a sorted list of keys (we only take the first key of each block) of the SSTable. Sparse Index is stored in the RAM.

Deletion - Tombstones

Naive Approach 1

  1. Delete the key from MemTable

Will this work? NO!

After this delete, if we try to read the value, we will end up searching the SSTables.

Effectively, this approach will not really delete the key, it will just undo the last key.

Naive Approach 2

  1. Delete the key from Memtable
  2. Delete the key from WAL
  3. Delete the key from all SSTables

This will certainly get rid of the key.

Incredibly expensive.

Note that SSTables are immutable. If you delete data, since you can't shift all the other data, there will be gaps in the disk

Tombstone (aka Sentinel / Flag / Marker / Guard) is a special marker that indicates that the value has been deleted.

Any deletes happen via writes.

TOMBSTONE = “PZpaIBk8rbaIQVoUqGD2NS04qD3gONn0QH1Cm2DKBkoktwGuEt”

// it is practically impossible for your data to contain this exact random string by sheer chance.

void set(key, value) {

    ...

}

void delete(key) {

    set(key, TOMBSTONE)

}

string _get(key) {

    // check memtable

    // check sstables

    // ...

}

string get(key) {

    value = _get(key)

    if (value == TOMBSTONE) {

        raise KeyNotFoundError!

    }

    return value

}

Note: Compaction can only delete Tombstones from the oldest SSTable (the one starting from SSTable 0)

If an SSTable is not the oldest, the tombstone entries must still be stored in the SSTable.

Final Structure & Algorithm

Writes

  1. We first append the entry into the WAL file (for durability)
  2. We then set the value in the Memtable (for fast reads)

The following events can be triggered after any write:

  • Flush: If the WAL file gets full, we flush it into a new SSTable.
  • Compaction: If there's too many SSTables on any level, we trigger compaction.
  • Eviction: If the MemTable gets full, we use LRU eviction to remove the oldest entry.

Deletions happen by setting the value to TOMBSTONE

Bloom Filter also gets updated for each write

Reads

  1. We first check the MemTable (which acts as a cache).
  1. If the data is found in the MemTable, then the value is guaranteed to the latest value
  1. because any changes first go to the MemTable (write-through) + WAL
  2. data in MemTable can never be stale
  1. Any recently written/accessed data is guaranteed to be in the MemTable
  2. Majority of the reads are incredibly fast — O(1) access in the RAM (if your cache hit ratio is high)
  3. Majority of the time, we won't even have to touch the disk
  4. Note that after reading the value, we must update the last accessed timestamp in the MemTable for that key.
  1. If we don't find the data in the MemTable
  1. Note that we don't have to check the WAL file
  1. because the MemTable is significantly larger than WAL and follows LRU eviction, it means that any data in the WAL will also be in the MemTable
  1. We must now scan ALL the SSTables one by one, in reverse order (starting from the most recent to the least recent).
    For each SSTable, do:
  1. Check if the key is present in the SSTable
  1. since the SSTable is sorted, this will O(log n) disk reads (n is the number of entries in the SSTable)
  2. First, Binary Search (lowerbound) the key in the Sparse Index from the RAM for this SSTable.
    The SparseIndex will tell us which block of the SSTable to read.
    this requires no disk reads, since the Sparse Index is in the RAM
  3. We will read the entire block into the RAM
    Reading the entire block takes just 1 disk access
  4. We can now Binary Search this block within the RAM
    RAM is 1 million times faster than disk ⇒ binary search in RAM is free
  5. If the key is found, then this must be the latest value (because we're scanning from recent to old)
    We can return this value
  6. If not found, we continue to the next older SSTable.
  1. If the key is not found in any SSTable, then we raise a KeyNotFoundError
  2. Once we find the value, we must update the MemTable so that any subsequent accesses for this key are fast

Note: during a read, if the value is found to be TOMBSTONE, we return a KeyNotFoundError

Isn't scanning all SSTables one by one a slow process?

Yes. This is why, we've the following optimizations

  1. Compaction: will reduce the number of SSTables.
  • Typically database LSM tree will have <= 10 SSTables
  1. Sparse Index: Binary Search on disk is slow. Reduce that to O(1) search.

Optimizing containment checks - Bloom Filter

If we try to get(key) for a key which was never inserted in the DB, then this leads to the slowest possible read - worst case for reads!

  • first check MemTable - we won't find it (never inserted)
  • scan each SSTable one by one - we won't find it (never inserted)

In a lot of databases, it is common to have to check if an entry was never inserted.

For example - signing up to a website - you have to create a username, this username must be distinct. The user will supply a unique username pragy1234 - we must ensure that this username doesn't exist in the DB already. This is an example of a read for a key that was never inserted.

  • Bloom Filter is a probabilistic Data Structure
  • Bloom Filters only support Inserts & Containment Checks.
    They do NOT support reads / updates / deletes / iteration
  • Containment checks can be faulty (it can lie to you)
  • False Positive is possible: If a key was not inserted in the bloom filter, it can still say that the key exists
  • False Negative is impossible: If a key was inserted in the bloom filter, it will NEVER say that the key does not exist.

BloomFilter is just a bit array.

  • Whenever we insert anything into our LSMTree, we will also insert the key into the bloom filter.
  • Whenever we read a value from the LSMTree, we will first check if the key exists in the Bloom Filter
  • Bloom Filter says "Yes, key exists" - we will read the LSM tree
  • it is possible for the key to be actually present in the database
  • it is also possible for the key to not be present in the database (bloom filter gave a false positive)
  • no issues - we just read the LSMTree for a key which was not present (worst case read)
  • but this will happen only rarely — the false positive rate will be low
  • Bloom Filter says "No, key not found":
  • guaranteed that this key was never inserted in the DB. Just return KeyNotFound!

void set(key, value) {

    bloom_filter.insert(key)

    // … proceed with the DB insertion

}

string get(key) {

    if(! bloom_filter.contains(key))

        raise KeyNotFound!

    // if bloom filter says key found

    // the DB might have the key, or might not have

       the key

    // proceed with normal DB check

}

On average, a properly tuned bloom filter uses only 10 bits per inserted key.

Resources (optional)